package Test.限流算法;

import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

/**
 * @Author: kirito
 * @Description:
 * 滑动窗口限流算法是一种常用的限流算法，用于控制系统对外提供服务的速率，防止系统被过多的请求压垮。
 * 它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。
 * 它可以解决固定窗口临界值的问题。
 *
 * 假设单位时间还是1s，滑动窗口算法把它划分为5个小周期，也就是滑动窗口（单位时间）被划分为5个小格子。
 * 每格表示0.2s。每过0.2s，时间窗口就会往右滑动一格。
 * 然后呢，每个小周期，都有自己独立的计数器，如果请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。
 *
 * 我们来看下，滑动窗口,去解决固定窗口限流算法的临界问题，思想是怎样
 *      假设我们1s内的限流阀值还是5个请求，0.8~1.0s内（比如0.9s的时候）来了5个请求，
 *      落在黄色格子里。时间过了1.0s这个点之后，又来5个请求，落在紫色格子里。
 *      如果是固定窗口算法，是不会被限流的，但是滑动窗口的话，每过一个小周期，它会右移一个小格。
 *      过了1.0s这个点后，会右移一小格，当前的单位时间段是0.2~1.2s，
 *      这个区域的请求已经超过限定的5了，已触发限流啦，实际上，紫色格子的请求都被拒绝啦。
 *
 *  当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
 *
 *  优点：
 *
 * 简单易懂
 * 精度高（通过调整时间窗口的大小来实现不同的限流效果）
 * 可扩展性强（可以非常容易地与其他限流算法结合使用）
 * 缺点：
 *
 * 突发流量无法处理（无法应对短时间内的大量请求，但是一旦到达限流后，请求都会直接暴力被拒绝。
 * 酱紫我们会损失一部分请求，这其实对于产品来说，并不太友好），需要合理调整时间窗口大小。
 * @Date: 2024/2/28 14:40
 * @Version: 1.0
 */

public class 滑动窗口 {
    /**
     * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
     */
    private int SUB_CYCLE = 10;

    /**
     * 每分钟限流请求数
     */
    private int thresholdPerMin = 100;

    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters = new TreeMap<>();

    /**
     * 滑动窗口时间算法实现
     */
    public synchronized boolean slidingWindowsTryAcquire() {
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
        int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数

        //超过阀值限流
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        //计数器+1
        Integer integer = counters.get(currentWindowTime);
        counters.put(currentWindowTime, ++integer);
        return true;

    }

    /**
     * 统计当前窗口的请求数
     */
    private int countCurrentWindow(long currentWindowTime) {
        //计算窗口开始位置
        long startTime = currentWindowTime - (long) SUB_CYCLE * (60/SUB_CYCLE-1);
        int count = 0;

        //遍历存储的计数器
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            // 删除无效过期的子窗口计数器
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                //累加当前窗口的所有计数器之和
                count =count + entry.getValue();
            }
        }
        return count;
    }
}
